#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    // vector<int> productExceptSelf(vector<int>& nums) {
    //     int subL = 1, subR = 1;

    //     vector<int> ret(nums.size(), 1);
    //     for (int left = 0, right = nums.size() - 1; left < nums.size(); left++, right--)
    //     {
    //         ret[left] *= subL;
    //         ret[right] *= subR;

    //         subL*= nums[left];
    //         subR *= nums[right];
    //     }

    //     return ret;
    // }

    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size(), 1);
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            if (i == nums.size() - 1)
                ret[i] = nums[i];
            else
                ret[i] = ret[i + 1] * nums[i];
        }
        vector<int> subL(nums);
        for (int i = 0; i < nums.size(); i++)
        {
            if (i == 0)
                subL[i] = nums[i];
            else
                subL[i] = subL[i - 1] * nums[i];
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (i == 0)
                ret[i] = ret[i + 1];
            else if (i == nums.size() - 1)
                ret[i] = subL[i - 1];
            else
                ret[i] = subL[i - 1] * ret[i + 1];
        }

        return ret;
    }
};